//
// Created by Jisam on 22/09/2024 7:03 PM.
// Solution of  简单图形问题 - 0123
#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while(t--){
        int k;
        cin >> k;
        int f1 = 0;
        int f2 = 0;
        if(sqrt(k) * sqrt(k) == k){
            f1 = 1;
        }
        if(sqrt((4 * k) / sqrt(3)) * sqrt((4 * k) / sqrt(3)) == k){
            f2 = 1;
        }
        if(f1 == 1){
            if(f2 == 1){
                cout << 2  << endl;
                break;
            }
            cout << 0 << endl;
            break;
        }else if(f2 == 1){
            cout << 1 <<endl;break;
        }else{
            cout << 3 <<endl;break;
        }
    }
    return 0;
}